package MiddlePractice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Demo743 {
//	743. 网络延迟时间
//	有 n 个网络节点，标记为 1 到 n。
//
//	给你一个列表 times，表示信号经过 有向 边的传递时间。 
//	times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
//
//	现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
	public int networkDelayTime(int[][] times, int n, int k) {
		k = k - 1;
		
		List<int[]>[] graph = createGraph(times, n);
		
		int[] minDistTo = new int[n];
		Arrays.fill(minDistTo, Integer.MAX_VALUE);
		minDistTo[k] = 0;
		
		PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> a.distFromStart - b.distFromStart);
		
		pq.offer(new State(k, 0));
		
		while(!pq.isEmpty()) {
			
			State state = pq.poll();
			int curVex = state.vexId;
			
			if(minDistTo[curVex] < state.distFromStart) {
				continue;
			}
			
			for(int[] nextVex : graph[curVex]) {
				int distToNext = minDistTo[curVex] + nextVex[1];
				if(distToNext < minDistTo[nextVex[0]]) {
					minDistTo[nextVex[0]] = distToNext;
					pq.offer(new State(nextVex[0], distToNext));
				}
			}
		}
		
		int max_res = 0;
		for(int i=0; i<minDistTo.length; i++) {
			if(minDistTo[i] == Integer.MAX_VALUE)
				return -1;
			max_res = Math.max(max_res, minDistTo[i]);
		}
		
		return max_res;
    }
	

	private List<int[]>[] createGraph(int[][] times, int n) {
		
		List<int[]>[] graph = new List[n];
		for(int i=0; i<n; i++) {
			graph[i] = new LinkedList<int[]>();
		}
		
		for(int i=0; i<times.length; i++) {
			int from = times[i][0] - 1;
			int to = times[i][1] - 1;
			int weight = times[i][2];
			graph[from].add(new int[] {to, weight});
		}
		
		return graph;
	}
	
	class State {
		public int vexId;
		public int distFromStart;
		public State(int vexId, int distFromStart){
			this.vexId = vexId;
			this.distFromStart = distFromStart;
		}
	}
	
}
